class Solution {
public:
    // int multiply(int A, int B) {
    //     //所谓的A*B其实就是有B个A相加即可，现在需要递归解决，那么我的每一层就加一个A即可
    //     if(B == 0)
    //         return 0;
    //     if(B == 1)
    //         return A;
    //     return A+multiply(A,B-1);
    // }//但是这样的时间复杂度就是O(B)了，优化就是让小数成为B，这样能够减少递归层数，继续优化，当递归到目标值的一半的
    //时候我们可以选择直接进行返回，也就是让此时的值*2即可，那么如何得到这个目标值的一半呢？继续一半二分这样最后的时间
    //复杂度就成为了log(B)
    //新解法
    int dfs(int big,int small)
    {
        if(small == 0)
        {
            return 0;
        }
        if(small == 1)
        {
            return big;
        }
        int half_small = small>>1;//通过位运算进行触发
        int half_sum = dfs(big,half_small);//一半的small和big的和
        if(small%2 == 0)
        {
            //代表是偶数个small
            return half_sum+half_sum;
        }
        else
        {
            //说明不是偶数个small
            return half_sum+half_sum+big;
        }
    }
    int multiply(int A, int B) {
        int small = A<B?A:B;
        int big = A>B?A:B;
        return dfs(big,small);
    }

};